package gold.digger;

import gold.utils.InputUtil;

import java.util.*;

/**
 * Created by fanzhenyu02 on 2021/12/10.
 * common problem solver template.
 */
public class LC691 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {
        int N = 20, M = 1 << 20, INF = 50;
        int[] f = new int[M];
        String[] ss;
        String t;

        int dfs(int state) {
            int n = t.length();
            if (state == ((1 << n) - 1)) return 0;
            if (f[state] != -1) return f[state];
            int ans = INF;
            for (String s : ss) {
                int nstate = state;
                out:
                for (char c : s.toCharArray()) {
                    for (int i = 0; i < n; i++) {
                        if (t.charAt(i) == c && ((nstate >> i) & 1) == 0) {
                            nstate |= (1 << i);
                            continue out;
                        }
                    }
                }
                if (nstate != state) ans = Math.min(ans, dfs(nstate) + 1);
            }
            return f[state] = ans;
        }

        public int minStickers(String[] stickers, String target) {
            ss = stickers;
            t = target;
            Arrays.fill(f, -1);
            int ans = dfs(0);
            return ans == INF ? -1 : ans;
        }
    }


    class Solution_Time_Exceed {

        Map<String, Integer> memo = new HashMap<>();

        public int minStickers(String[] stickers, String target) {
            int n = stickers.length, ans = Integer.MAX_VALUE;
            int[][] stickerSimplify = new int[n][26];
            int[] targetSimplify = new int[26], stickerTotal = new int[26];
            for (int i = 0; i < target.length(); i++) {
                targetSimplify[target.charAt(i) - 'a']++;
            }

            for (int j = 0; j < n; j++) {
                for (int i = 0; i < stickers[j].length(); i++) {
                    stickerSimplify[j][stickers[j].charAt(i) - 'a']++;
                    stickerTotal[stickers[j].charAt(i) - 'a'] = 1;
                }
            }

            for (int i = 0; i < 26; i++) {
                if (targetSimplify[i] > 0 && stickerTotal[i] <= 0) return -1;
            }

            return dfs(stickerSimplify, targetSimplify);
        }

        public int dfs(int[][] stickerSimplify, int[] targetSimplify) {
            if (isMatch(targetSimplify)) return 0;
            if (memo.containsKey(Arrays.toString(targetSimplify))) return memo.get(Arrays.toString(targetSimplify));

            int curMinAns = Integer.MAX_VALUE;
            for (int[] sticker : stickerSimplify) {
                int[] copyTarget = copyArray(targetSimplify);
                // choose current sticker.
                for (int i = 0; i < 26; i++) {
                    targetSimplify[i] = Math.max(0, targetSimplify[i] - sticker[i]);
                }

                if (Arrays.toString(targetSimplify).equals(Arrays.toString(copyTarget))) {
                    // current choose cannot make any effect, continue to take next
                    continue;
                }

                int chooseCurrent = dfs(stickerSimplify, targetSimplify) + 1;
                curMinAns = Math.min(curMinAns, chooseCurrent);
                targetSimplify = copyTarget;
            }

            memo.put(Arrays.toString(targetSimplify), curMinAns);
            return curMinAns;
        }

        public boolean isMatch(int[] targetSimplify) {
            for (int cnt : targetSimplify) {
                if (cnt > 0) return false;
            }

            return true;
        }

        public int[] copyArray(int[] targetSimplify) {
            int[] copy = new int[26];
            for (int i = 0; i < 26; i++) {
                copy[i] = targetSimplify[i];
            }

            return copy;
        }
    }

    public void run() {
        System.out.println(new Solution().minStickers(new String[]{"with", "example", "science"}, "thehat"));
        System.out.println(new Solution().minStickers(new String[]{"notice", "possible"}, "basicbasic"));
    }

    public static void main(String[] args) throws Exception {
        LC691 an = new LC691();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
